#include <vector>
#include <unordered_map>
#include <string>
#include <cstdio>
using namespace std;


// version 1
class Solution {
public:
    string minWindow(string s, string t) {
        if (t.size() > s.size()) return "";

        //用于统计字符出现的次数的
        int s_hash[128] = { 0 }, t_hash[128] = { 0 }, useful_ch_num = 0;

        //先统计t的情况
        for (auto& ch : t) t_hash[ch]++;

        int cnt = t.size();

        string ret;
        for (int left = 0, right = 0; right < s.size(); ++right) {
            //1.入窗口前，需要判断一下有效数据
            char in = s[right];
            //统计有效数据逻辑
            if (s_hash[in] < t_hash[in])
                ++useful_ch_num;

            //入窗口
            if(t_hash[in] != 0) s_hash[in]++;

            while (useful_ch_num == cnt) {

                //针对于很可能前面出现一连串的相同的，再次优化
                for (int i = left; i < right; ) {
                    if (s[i] == s[i + 1] && s_hash[s[i]] > t_hash[s[i]]){
                        s_hash[s[i]]--;
                        ++i;
                    } 
                    else {
                        left = i;
                        break;
                    }
                }


                //先更新结果（前提是 useful_ch_num == t.size()）
                string tmp;
                tmp = s.substr(left, right - left + 1);
                if (useful_ch_num == cnt && (ret == "" || tmp.size() < ret.size())) ret = tmp;

                char out = s[left++];
                //有效数据处理
                if (t_hash[out] != 0 && s_hash[out] <= t_hash[out]) --useful_ch_num;
                //出窗口
                if(s_hash[out] != 0) s_hash[out]--;

                //然后开始判断，后面要是有一堆不存在于t的字符，就一直跳过
                while(left < s.size() && t_hash[s[left]] == 0)
                    ++left;
                if(right < left) right = left - 1;
            }
        }
        return ret;
    }
};










//version 2
class Solution {
//针对于每一次都使用子串赋值来搞，耗费时间 + 内存，这里先标记长度和起始位置
//最后来操作
public:
    string minWindow(string s, string t) {
        int s_hash[128] = {0}, t_hash[128] = {0}, useful_num = 0;

        //先统计t中的情况
        for(auto& ch : t) t_hash[ch]++;
        int cnt = t.size();

        int minlen = 0xffffffff, begin = -1;
        for(int left = 0, right = 0; right < s.size(); ++right){
            //入窗口
            char in = s[right];
            if(s_hash[in] < t_hash[in]) ++useful_num;
            if(t_hash[in]) s_hash[in]++; //对于不存在于t串中的字符，没有必要进入哈希表

            //这里不太一样，是窗口符合条件得出窗口
            while(useful_num == cnt){
                if (right - left + 1 < minlen) {
                    minlen = right - left + 1;
                    begin = left;
                }

                //出窗口
                char out = s[left++];
                if(t_hash[out] && s_hash[out] <= t_hash[out]) --useful_num;
                if(t_hash[out]) s_hash[out]--; //对于不存在于t串中的字符，没有必要进入哈希表，也没办法出哈希表
            }
        }

        if(begin == -1) return "";
        else return s.substr(begin, minlen);
    }
};

//version 1的基本思想就是上面这样，只不过说，使用了大量的string tmp来进行赋值，这影响了时间复杂度和空间复杂度
//所以，第二个版本还是一样的思想，只不过选取字串的时候我们通过起始位置和长度来操作